package com.yww.algorithm.recursion;

/**
 * @author yww
 * @description 递归二分查找
 * @since 2024/1/31 11:39
 */
public final class BinarySearch {
    public static void main(String[] args) {
        int[] arr = new int[]{12, 13, 56, 78};
        System.out.println(binarySearch(arr, 566));
    }

    public static int binarySearch(int[] arr, int target) {
        return f(arr, target, 0, arr.length - 1);
    }

    private static int f(int[] arr, int target, int i, int j) {
        // 结束条件
        if (j < i) {
            return -1;
        }

        int m = (i + j) >>> 1;
        if (target < arr[m]) { // 在右侧，j 缩小
            return f(arr, target, i, m - 1);
        } else if (arr[m] < target) { // 在左侧，i扩大
            return f(arr, target, m + 1, j);
        } else {
            return m;
        }
    }
}
